package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/10/8 11:59
 * @Description:删除BST的节点
 */
public class Num450_DeleteBSTNode {
    /**
     * 在以root为根的BST中删除值为key的节点，返回删除后的根节点
     * Hebaird Deletion
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        // base case
        if (root == null) {
            return null;
        }
        if(root.val < key) {
            // 右树删除
            root.right = deleteNode(root.right,key);
        }else if (root.val > key) {
            // 左树删除
            root.left = deleteNode(root.left,key);
        }else {
            // 当前节点就是待删除的节点
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            // 找到当前树的后继节点
            TreeNode successor = findSuccessor(root.right);
            successor.right = deleteMin(root.right);
            successor.left = root.left;
            return successor;
        }
        return root;
    }

    /**
     * 在当前以root为根的BST中删除最小值后返回树根
     * @param root
     * @return
     */
    private TreeNode deleteMin(TreeNode root) {
        if (root.left == null) {
            // 当前节点就是最小值节点
            return root.right;
        }
        // 一定要记得更新左子树树根的引用
        root.left = deleteMin(root.left);
        return root;
    }

    private TreeNode findSuccessor(TreeNode root) {
        if (root.left == null) {
            return root;
        }
        return findSuccessor(root.left);
    }
}
